#include <stdio.h>
#include <stdlib.h>
#include "sqqueue.h"
#include "sqstack.h"

typedef char ElemType;
typedef struct BTNode {
    ElemType data;
    struct BTNode *lchild, *rchild;
} BTNode, *BiTree;

void visit(BiTree t) { printf("%c ", t->data); }

// 层序创建二叉树
void LevelOrderCreateBiTree(BiTree* t, ElemType a[], int n) {
    if (n <= 0) {
        *t = NULL;
        return;
    }
    SqQueue q;
    InitQueue(&q);
    EnQueue(&q, t);
    for (int i = 0; i < n && !QueueEmpty(&q); ++i) {
        BiTree* p;
        DeQueue(&q, (void**)&p);
        if (a[i] != '#') {
            *p = (BiTree)malloc(sizeof(BTNode));
            if (!*p) {
                return;
            }
            (*p)->data = a[i];
            (*p)->lchild = (*p)->rchild = NULL;
            EnQueue(&q, &((*p)->lchild));
            EnQueue(&q, &((*p)->rchild));
        }
    }
}

// 递归先序遍历
void PreOrderVisit(BiTree t) {
    if (!t) return;
    visit(t);
    PreOrderVisit(t->lchild);
    PreOrderVisit(t->rchild);
}

// 递归中序遍历
void InOrderVisit(BiTree t) {
    if (!t) return;
    InOrderVisit(t->lchild);
    visit(t);
    InOrderVisit(t->rchild);
}

// 递归后序遍历
void PostOrderVisit(BiTree t) {
    if (!t) return;
    PostOrderVisit(t->lchild);
    PostOrderVisit(t->rchild);
    visit(t);
}

// 非递归先序遍历
void PreOrderVisit2(BiTree t) {
    SqStack s;
    InitStack(&s);
    while (t || !StackEmpty(&s)) {
        if (t) {
            visit(t);   // 先访问当前子树的根结点
            push(&s, t);    // 将当前子树的根结点入栈
            t = t->lchild;  // 优先访问当前子树的左子树
        } else {
            pop(&s, (void**)&t);  // 弹出最近访问子树的根结点
            t = t->rchild;        // 访问当前子树的右子树
        }
    }
}

// 非递归中序遍历
void InOrderVisit2(BiTree t) {
    SqStack s;
    InitStack(&s);
    while (t || !StackEmpty(&s)) {
        if (t) {
            push(&s, t);    // 将当前子树的根结点入栈
            t = t->lchild;  // 优先访问当前子树的左子树
        } else {
            pop(&s, (void**)&t);  // 弹出最近访问子树的根结点
            visit(t);         // 访问当前子树的根结点
            t = t->rchild;        // 访问当前子树的右子树
        }
    }
}

// 非递归后序遍历
void PostOrderVisit2(BiTree t) {
    SqStack s;
    InitStack(&s);
    BiTree last = NULL;  // 记录最近访问过的结点
    while (t || !StackEmpty(&s)) {
        if (t) {
            push(&s, t);    // 将当前子树的根结点入栈
            t = t->lchild;  // 优先访问当前子树的左子树
        } else {
            GetTop(&s, (void**)&t);  // 取出栈顶结点，不弹出
            if (t->rchild && t->rchild != last) {
                t = t->rchild;  // 当前子树的右子树存在且未被访问过，访问当前子树的右子树
            } else {
                pop(&s, (void**)&t);  // 弹出最近访问子树的根结点
                visit(t);         // 访问当前子树的根结点
                last = t;             // 记录最近访问过的结点
                t = NULL;             // 置空，继续弹出栈顶结点
            }
        }
    }
}

// 层次遍历
void LevelOrderVisit(BiTree t) {
    if (!t) {
        return;  // 空树直接返回
    }
    SqQueue q;
    InitQueue(&q);
    EnQueue(&q, t);
    while (!QueueEmpty(&q)) {
        BiTree p;
        DeQueue(&q, (void**)&p);
        visit(p);  // 访问队头结点
        if (p->lchild) {
            EnQueue(&q, p->lchild);  // 如果有左孩子，将左孩子入队
        }
        if (p->rchild) {
            EnQueue(&q, p->rchild);  // 如果有右孩子，将右孩子入队
        }
    }
}